<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
A Complete Example of a CHR File
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial111.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial107.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial113.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc221">15.5</A>&nbsp;&nbsp;A Complete Example of a CHR File</H2><UL>
<LI><A HREF="tutorial112.html#toc111">CHR Implementation</A>
</UL>

Sometimes whole sets of constraints can be combined.
Consider, for example, a program where disequalities on pairs of
variables are accumulated during search.
Whenever a point is reached where any subset of the variables are all
constrained to be different an <CODE>alldifferent</CODE> constraint can be
posted on that subset, thus supporting more powerful propagation.
This can be achieved by finding <EM>cliques</EM> in the graph whose nodes
are variables and edges are disequality constraints.<BR>
<BR>
<A NAME="@default402"></A>
We start our code with a declaration to load the <EM>ech</EM> library.
The constraints are then declared, and subsequently defined by rules.
The CHR encoding starts by generating a clique whenever two variables
are constrained to be different.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(ech).
:- constraints neq/2.

neq(X,Y) ==&gt;
    sort([X,Y],List),
    clique(List),
    neq(Y,X).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Each clique is held as a sorted list to avoid any duplication.
The symmetrical disequality is added to simplify the detection of new
cliques, below.
Whenever a clique is found, the <CODE>alldifferent</CODE> constraint is
posted, and the CHRs seek to extend this clique to
include another variable:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- constraints clique/1.

clique(List) ==&gt; alldifferent(List).
clique(List),neq(X,Y) ==&gt;
    in_clique(Y,List), not in_clique(X,List) |
    sort([X|List],Clique),
    extend_clique(X,List,Clique).

in_clique(Var,List) :-
    member(El,List), El==Var, !.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The idea is to search the constraint store for a disequality between
the new variable <CODE>X</CODE> and each other variable in the original
clique. This is done by recursing down the list of remaining
variables.
When there are no more variables left, a new clique has been found.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
neq(X,Y) <CODE>\</CODE> extend_clique(X,[Y|Tail],Clique) &lt;=&gt;
    extend_clique(X,Tail,Clique).
extend_clique(_,[],Clique) &lt;=&gt; 
    clique(Clique).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Finally, we add three optimisations.
Don't try and find a clique that has already been found, or
find the same clique twice. If the new variable is equal to a
variable in the list, then don't try any further.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
clique(Clique) <CODE>\</CODE> extend_clique(_,_,Clique) &lt;=&gt; true.
extend_clique(_,_,Clique) <CODE>\</CODE> extend_clique(_,_,Clique) &lt;=&gt; true.
extend_clique(Var,List,_) &lt;=&gt; in_clique(Var,List) | true.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
<A NAME="toc111"></A>
<H3 CLASS="subsection"><A NAME="htoc222">15.5.1</A>&nbsp;&nbsp;CHR Implementation</H3>
CHR's are implemented using the ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> suspension and waking
mechanisms. 
A rule is woken if:
<UL CLASS="itemize"><LI CLASS="li-itemize">
a new goal is posted, which matches one of the goals in its head
<LI CLASS="li-itemize">a goal which has already been posted earlier becomes further
instantiated.
</UL>
<A NAME="@default403"></A>
The rule cannot fire unless the goal is more instantiated than the
rule head. Thus the rule
<CODE>p(a,f(Y),Y) &lt;=&gt; q(Y)</CODE> is really a shorthand for the guarded
rule:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
p(A,B,C) &lt;=&gt; A=a, B=f(Y), C=Y | q(Y)
</PRE></BLOCKQUOTE>
The guard is &#8220;satisfied&#8221; if, logically, it is entailed by the
constraints posted already.<BR>
<BR>
In practice the CHR implementation cannot always detect the
entailment.
The consequence is that goals may fire later than they could.
For example consider the program

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- constraints p/2.
p(X,Y) &lt;=&gt; ic:(X $&gt; Y) | q(X,Y).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
and the goal
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?-  ic:(X $&gt; Y),
    p(X,Y).
</PRE></BLOCKQUOTE>
Although the guard is clearly satisfied, the CHR implementation cannot
detect this and <CODE>p(X,Y)</CODE> does not fire.
If the programmer needs the entailment of inequalities to be detected,
it is necessary to express inequalities as CHR constraints, which
propagate <TT>ic</TT> constraints as illustrated in the example
<CODE>prec(S1,D,S2)</CODE> above.<BR>
<BR>
CHRs can detect entailment via variable bounds, so <CODE>p(X,0)</CODE>
does fire in the following example:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?-  ic:(X $&gt; 1),
    p(X,0).
</PRE></BLOCKQUOTE>
The implementation of this entailment test in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> is to impose
the guard as a constraint, and fail (the entailment test) as soon as
any variable becomes more constrained.
A variable becomes more constrained if:
<UL CLASS="itemize"><LI CLASS="li-itemize">
it becomes more instantiated
<LI CLASS="li-itemize">its domain is tightened
<LI CLASS="li-itemize">a new goal is added to its suspension list
</UL>
There are many examples of applications expressed in CHR in the
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> distribution.
They are held as files in the <EM>chr</EM> subdirectory of the standard
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> library directory <EM>lib</EM>. <BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
CHRs suspend on the variables in the rule head. On waking the CHR
tests if its guard is entailed by the current constraint store. The
entailment test is efficient but incomplete, and therefore rules may
fail to fire as early as they could in theory.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 15.6: CHR Implementation</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial111.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial107.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial113.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
